package OJPractice;
/*
* 面试可能被问道：
* 一. 项目中发现了什么bug？
*     我写了两个版本的测试，一个是单机项目的版本，第二个版本就是项目部署到云服务器之后的测试版本，单机版本的测试
* 就是在bug出现的过程中，就已经把bug修复了，部署到服务器的版本有这么几个bug：
* 1. 注册失败，定位这个bug就是根据前端显示的这个报错信息
* 因为在后端的统一处理数据返回的模块中我的逻辑就是如果出bug了，就封装成ajaxResult响应返回给前端的报错信息，方便定位这个bug，看这个
* 报错信息就发现：密码长度过长，导致 Mariadb数据库无法存储这个密码数据，比如设置密码123也能登录进去，但是数据库中存储的是加盐算法处理
* 之后的密码，解决方案：就是修改一下 Mariadb数据库中的密码字段的长度即可
* 2. 登录获取不到验证码图片：定位这个bug就是抓包看前端ajax请求数据和参数是正确发送，后观察后端接口中是否绑定了这个参数， 发现响应的数据
* 为 null，所以这个就是后端的问题，我就去看储存验证码的路径下对应的文件是否有对应生成的验证码图片，发现后端 后端 properties 配置文件错误，
* 项目部署到云服务器后需要新建文件夹来存储生成的验证码图片，解决方案：停止当前项目运行并杀死8080端口对应的进程，止呕修改项目拍杂志文件中的
* 验证码存储路径，重新打jar包并将jar包上传到服务器上，创建对应的晚间加存储验证码图片，重启项目，发现bug已经解决
* 3. 博客发布时间为 null，就是新发布的博客不显示博客的发布时间，而是显示 null，定位bug就是抓包观察响应信息，发现参数返回的就是 null，
* 发现是后端的问题，就检查了一下数据库中表结构以及说设置这个字段的初始值是否是错误的，就找到了bug，原因就是当前服务器中 Mariadb5.5
* 版本一下数据库不支持 timestamp类型，而且是不允许设置默认值的，解决方案：更新数据库的版本为10以上，然后更改表结构设置发布博客时间默认值
* 是当前时间，最后重启 Mariadb 数据库，将项目重新打包到服务器上
* 4. 点赞数量不增加：定位bug，把数据库中的默认字段（点赞状态，点赞数量）设置成0即可
* */
/*
* 针对MQ项目是如何进行测试的？
* 主要是进行的单元测试和客户端程序测试服务器的逻辑是否正确，单元测试中每一个类中又包含了很多组单元测试用例，测试的类主要有：
* 大体上所有测试类都又前置工作和收尾工作：1. 拿到 Spring中的context对象，启动MQ项目，对数据库进行初始化的一些操作
* 收尾工作就是：先关闭context对象，因为这个context对象是持有了MetaMapper的实例的，实例又打开了数据文件，此时的删除是不会成功的
* 把数据库上的数据和数据文件中的数据清空，
* 1.硬盘数据管理类：创建，删除，插入：交换机，队列，绑定，针对这些概念中的属性设置一些参数，使用断言测试看预期是否符合结果
* 2.内存存储的数据：针对数据在内存上是否能够正常存储，首先插入交换机，队列，绑定，消息之类的，还是设置一些参数，之后看结果是偶
* 符合预期，包含测试往队列中插入消息，取出消息，看插入的消息和取出的消息是否是一致的，测试将消息加入到未被确认消息队列中
* 还有就是把内存的消息保存到硬盘中，最后清理硬盘中的数据
* 3.虚拟主机类：创建好需要测试的交换机，队列，绑定之后，先有消费者订阅队列，之后发送消息，消费消息，之后看这些都是否符合预期
* */
/*对博客系统是如何测试的？
主要用到的是自动化测试：就看当前web项目中哪些需要进行自动化测试
* 之后针对这些模块设计测试用例，之后手工测试一些主要功能测试，之后根据设计的自动化测试用例编写测试代码，用的工具是 selenium 和 junit5
先使用 selenium 针对单个模块进行测试，之后使用junit中的测试套件将测试类串联起来，整体进行测试
*/
/*
* 都有什么测试方法？
* 按照是否查看代码划分：黑盒，白盒，灰盒测试
* 按照开发阶段：单元，集成，系统，验收测试
* 按照是否手工测试：手工测试，自动化测试
* 按照实施组织划分：α测试，β测试
* 按照测试对象划分：界面，易用性，容错，安全，性能，兼容，易用性，安装卸载，内存泄露
* */
/*
* 自动化测试里的登录删除测试，如果没有文章了删除测试怎么做？
* */
/*
* 为什么投递测试？
* 从个人爱好来说：我是比较对保证项目质量这一方面的业务和工作比较感兴趣，但是随着我对测试的深入的学习发现测试人员也需要有一些开发的基础
* 比如开发一些效能工具（如自动化测试工具）来辅助测试人员提高项目测试的效率
* 从工作性质来说：测试不仅仅包含黑盒测试，还有白盒测试，测试人员也需要扎实的开发基础来提高项目测试质量
* */
/*
* 对自己项目做过哪些测试工作？
* 1. 编写测试用例
* 2. 自动化测试，针对自己的项目主要有以下几个点：登录测试，个人详情页测试，写博客并发布测试，校验已发布博客标题和时间，删除，
* 注销账号等等一系列的测试用例代码的编写
* ，详情请看我简历中的自动化测试报告
* */
/*
* 自己学的测试工具有哪些？
* selenium 自动化测试工具，
* Juint单元测试框架，包含一些测试套件，
* Postman：主要用于接口测试，包括模仿各种类型的请求，
* fiddle：抓包工具，也可以用来测试接口，还可以用来模拟一些弱网
* LoadRunner：主要用于性能测试，包括三个*/
/*说说单元测试？
* 首先单元测试是属于白盒测试，不仅是测试人员需要写这种测试，开发人员也会写一些响应的单元测试测试接口之类的，单元测试的对象并没有明确
* 的标准，他可以是一个方法，类，功能模块，或者子系统，是软件测试中基础的测试类型，用于测试单独的模块是否可以正常工作。
* */
/*
* 针对 求两个公共字符串的子串如何设计测试用例？
* 假设我们有两个字符串A和B，并且它们有多个公共子串。我们可以设计以下测试用例来验证这些公共子串：
检查两个字符串是否都包含相同的公共子串。例如，如果A = "hello world"，B = "world hello"，则它们的公共子串包括
* “hello”和“world”。
检查一个字符串是另一个字符串的子串。例如，如果A = "apple"，B = "pineapple"，则它们的公共子串包括“p”、“e”、“a”和“l”。
检查一个字符串不是另一个字符串的子串。例如，如果A = "banana"，B = "grapefruit"，则它们的公共子串包括“a”、“n”和“g”
检查两个字符串之间是否有重叠的公共子串。例如，如果A = "hello world"，B = "goodbye world"，则它们的公共子串包括
* “hello”和“world”，但不包括“goodbye”。
检查两个字符串之间的相对位置关系是否影响它们的公共子串。例如，如果A = "abcdefg"，B = "bcdefga"，则它们的公共子串包括
* “bcd”和“efg”，但如果将它们的位置互换，则它们的公共子串变为“acb”和“cde”。
* */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

// 笔试面试真题编程题详解
/*
* leetCode 经典面试150道题*/
public class realPractice {
    // 合并两个有序数组
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] < nums2[j]) {
                nums1[k--] = nums2[j--];
            } else {
                nums1[k--] = nums1[i--];
            }
        }
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }

    // 下面两道移除元素的题目都是用双指针来解决
    // 移除元素(原地移除数组中等于 val 的元素，不能开辟新的空间)
    public int removeElement(int[] nums, int val) {
        int left = 0, right = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }
    // 删除有序数组中的重复项 II
    // 如果数组中出现了两个以上的重复的元素，就删除掉多余的，只保留两个相同的元素
    // 双指针，思路就是给定的数组是有序的，所以如果有重复的元素一定是相邻的，
    // 如果 nums[slow - 2] 和 nums[fast]相等，这块数组中的三个元素就是相等的
    // 就出现了两个以上的相等的元素，就让 fast++，一直走到不相等，将fast位置的元素赋值给slow位置
    // 也即是说相等就让fast++，不相等的时候就把fast的值赋值给slow下标
    public int removeDuplicates(int[] nums) {
        int slow = 2;
        int fast = 2;
        int n = nums.length;
        if (n < 2) return n;
        while (fast < n) {
            if (nums[slow - 2] != nums[fast]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
    // 多数元素
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
    // 轮转数组
    //  思路：反转整个数组，再翻转两个区间内的数组
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
            left++;
            right--;
        }
    }
    // 买卖股票的最佳时机
    // 思路：就是如何让两数之差最大，但是有一个条件就是后边的数一定 > 前边的数
    public int maxProfit(int[] nums) {
        int l = 0;
        int r = 1;
        int res = 0;
        for (int i = 0; i < nums.length && r < nums.length; i++) {
            if (nums[l] >= nums[r]) {
                l++;
            } else {
                if (res < nums[r] - nums[l]) {
                    res = nums[r] - nums[l];
                }
            }
            r++;
        }
        return res;
    }

    // 优选算法课程：数组划分
    // 移动零
    public void moveZeroes(int[] nums) {
        for (int cur = 0,dest = -1; cur < nums.length; cur++) {
            if (nums[cur] != 0) {
                dest++;
                swap(nums, cur, dest);
            }
        }
    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    // 复写零
    public void duplicateZeros(int[] arr) {
        int cur = 0;
        int dest = 0;
        while (dest < arr.length) {
            if (arr[cur] == 0) dest += 2;
            else dest++;
            if (dest >= arr.length - 1) break;
            cur++;
        }
        // 处理边界条件
        if (dest == arr.length) {
            arr[arr.length - 1] = 0;
            cur--;
            dest -= 2;
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[cur] != 0) {
                arr[dest--] = arr[cur--];
            } else {
                // 等于 0 的情况
                arr[dest++] = 0;
                arr[dest] = 0;
            }
        }
    }
    // 盛最多水的容器
    // 双指针解决，还有单调性
    public int maxArea(int[] nums) {
        int left = 0, right = nums.length - 1, max = 0;
        while (left < right) {
            int ret = Math.min(nums[left], nums[right]) * (right - left);
            if (nums[left] < nums[right]) left++;
            else right--;
            if (max < ret) max = ret;
        }
        return max;
    }
    // 有效三角形
    public int triangleNumber(int[] nums) {
        int ret = 0;
        Arrays.sort(nums);
        int i = nums.length - 1;
        while(i > 1) {
            int left = 0, right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    ret += right - left;
                    right--;
                } else {
                    left++;
                }
            }
            i--;
        }
        return ret;
    }
    // 三数之和
    // 这个题和牛客的三数之和不一样，需要考虑去重元素
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n; ) {
            if (nums[i] > 0) break;
            int left = i + 1, right = n - 1, target = -nums[i];
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum < target) left++;
                else if (sum > target) right--;
                else {
                    ret.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[left], nums[right])));
                    left++; right--;
                    while(left < right && nums[left] == nums[left - 1]) left++;
                    while(left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            i++;
            while(i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
    // 四数之和
    public List<List<Integer>> fourSum(int[] nums, int target) {
        // 双层for 循环，内部是一个双指针
        Arrays.sort(nums);
        int n =  nums.length;
        List<List<Integer>> ret = new ArrayList<>();
        for (int i = 0; i < n; ) {
            int tmp = target - nums[i];
            for (int j = i + 1; j < n; ) {
                int left = j + 1, right = n - 1;
                int target2 = target - nums[i] - nums[j];
                while (left < right) {
                    int sum = nums[left] + nums[right];
                    if (sum < target2) left++;
                    else if (sum > target2) right--;
                    else {
                        ret.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[left], nums[right])));
                        left++; right--;
                        // 去重
                        while (left < right && nums[left] == nums[left - 1]) left++;
                        while (left < right && nums[right] == nums[right + 1]) right--;
                    }
                }
                j++;
                while (j < n && nums[j] == nums[j - 1]) j++;
            }
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }

    // 无重复字符的最长子串
    public int lengthOfLongestSubstring(String ss) {
        char[] s = ss.toCharArray();
        // 用数组模拟哈希表
        int[] hash = new int[128];
        int left = 0, right = 0, n = ss.length();
        int ret = 0;
        while (right < n) {
            hash[s[right]]++; // 进入窗口
            while (hash[s[right]] > 1) { // 判断
                // 如果进入到这个while 循环，此时说明已经出现了重读的字符
                hash[s[left++]]--; // 数组对应的下标的值--，就是把这个重复的
            }
            // 字符去掉了
            ret = Math.max(ret, right - left + 1);
            right++; // 让下一个字符
        }
        return ret;
    }

    // 连续最大1的个数
    public int longestOnes(int[] nums, int k) {
        int ret = 0;
        for (int left = 0, right = 0, count = 0; right < nums.length; right++) {
            if (nums[right] == 0) count++;
            while (count > k) {
                if (nums[left++] == 0) count--;
            }
            ret = Math.max(ret, right - left + 1);
        }
        return ret;
    }

    // 字母大小写全排列
    List<String> ret;
    StringBuilder path;
    public List<String> letterCasePermutation(String s) {
        ret = new ArrayList<>();
        path = new StringBuilder();
        dfs(s, 0);
        return ret;
    }
    public void dfs(String s, int pos) {
        if (pos == s.length()) {
            ret.add(path.toString());
            return;
        }
        char ch = s.charAt(pos);
        if (ch < '0' || ch > '9') {
            path.append(change(ch));
            dfs(s, pos + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
    public char change(char ch) {
        if (ch >= 'a' && ch <= 'z') return ch -= 32;
        else return ch += 32;
    }
}


